package arithmetic.LeetCode;

import utils.ListNodeUtils;
import utils.ListNodeUtils.ListNode;

/**
 * 86. 分隔链表
 * 给你一个链表的头节点 head 和一个特定值 x ，请你对链表进行分隔，使得所有 小于 x 的节点都出现在 大于或等于 x 的节点之前。
 *
 * 你应当 保留 两个分区中每个节点的初始相对位置。
 *
 * 示例 1：
 * 输入：head = [1,4,3,2,5,2], x = 3
 * 输出：[1,2,2,4,3,5]
 *
 * 示例 2：
 * 输入：head = [2,1], x = 2
 * 输出：[1,2]
 *
 * 链接：https://leetcode.cn/problems/partition-list
 *
 * @author jiangfeng on 2023/7/25
 */
public class PartitionList {


    public static void main(String[] args) {
        ListNode link = ListNodeUtils.createLink(1, 4, 3, 2, 5, 2);
        ListNodeUtils.printLink(new Solution().partition(link,3));


    }

    static class  Solution {
        public ListNode partition(ListNode head, int x) {
            if(head==null||head.next==null){
                return head;
            }
            ListNode tempBig = new ListNode(-1);
            ListNode tempSmall = new ListNode(-1);
            ListNode tempHead = new ListNode(-1,head);
            ListNode p = tempHead,s = tempSmall,b = tempBig;
            while(p.next!=null){
                if(p.next.val<x){
                    s.next=p.next;
                    s=s.next;
                }else{
                    b.next=p.next;
                    b=b.next;
                }
                p=p.next;
            }
            b.next = null;
            s.next=tempBig.next;
            return tempSmall.next;
        }
    }


    static class Solution2 {
        public ListNode partition(ListNode head, int x) {
            ListNode small = new ListNode(-1);
            ListNode tempHead = new ListNode(-1,head);
            ListNode p = tempHead,sp = small;
            while(p.next!=null){
                if(p.next.val<x){
                    sp.next=p.next;
                    sp=sp.next;
                    // 原链移除这个
                    p.next=p.next.next;
                }else {
                    p=p.next;
                }

            }
            sp.next=tempHead.next;
            return small.next;
        }
    }
}
